1. Technical Field
This invention is directed toward a system and method for location and precision encoding. More specifically, the invention is directed toward a system and method for combining the precision estimate of a database entry's coordinate value such that the precision information is included as part of a one-dimensional index.
2. Background Art
Geographic Information Systems (GIS) are well-organized databases of information catalogued, in part, by their relationship to geography. Often, these databases contain on the order of millions or billions (or more) of data elements, each of which is associated with a particular geographical location. As an example, consider a world-wide photo database, where each photograph is associated with the location where it was taken.
Although modern relational databases perform a variety of algorithmic optimizations to speed up the retrieval of data contained in them, they remain inefficient at particular tasks. For example, databases are relatively poor at performing range queries over more than a single dimension. These are queries of the form, “Retrieve all data in which Value X is between x1 and x2, Value Y is between y1 and y2, and Value Z is between z1 and z2.” (Again, modern databases can handle even these types of queries well, if the number of data elements is comparatively small; but as they cannot know the form of the data a priori, they necessarily are designed for generality at the expense of efficiency, and remain inefficient for large amounts of data.)
Furthermore, in some GIS applications, elements are associated with geographical regions at different scales, and queries may be performed over a range of scales. For example, in a photo database, an item may be associated with the city of New York as a whole or more specifically with the city block representing the Empire State Building. In certain kinds of queries, it may be useful to retrieve all items taken at the Empire State Building when querying for photos taken in New York City, but the converse may be undesirable—not all photos taken in New York City will be relevant to a query about the Empire State Building.
Therefore, what is needed is a system and method that can create a database of location-tagged data, for which retrieval performance is optimized for location-based queries at a particular scale and finer, no matter of the massiveness of the database.